package LeetCode.LeetCodeHot;

import java.util.Arrays;

/**
 * 寻找两个正序数组的中位数
 * @author lumin
 * @date 2022/03/23 12:14
 **/
public class Num4 {
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if(nums1.length == 0){
            if(nums2.length % 2 == 0){
                return (nums2[nums2.length / 2] + nums2[(nums2.length / 2)] - 1) / 2.0;
            }else{
                return nums2[nums2.length / 2];
            }
        }
        if(nums2.length == 0){
            if(nums1.length % 2 == 0){
                return (nums1[nums1.length / 2] + nums1[(nums1.length / 2)] - 1) / 2.0;
            }else{
                return nums1[nums1.length / 2];
            }
        }
        int[] leftNums = new int[(nums1.length + nums2.length) >> 1];
        int midNum = (nums1.length + nums2.length) >> 1;
        int l = 0;
        int i = 0;
        int j = 0;
        int shuren = 1;
        while(l < leftNums.length){
            if(i == nums1.length){
                leftNums[l] = nums2[j];
                j++;
                l++;
                continue;
            }
            if(j == nums2.length){
                leftNums[l] = nums1[i];
                i++;
                l++;
                continue;
            }
            if(nums1[i] < nums2[j]){
                leftNums[l] = nums1[i];
                i++;
                l++;
            }else if(nums1[i] > nums2[j]){
                leftNums[l] = nums2[j];
                j++;
                l++;
            }else{
                if(shuren > 0){
                    leftNums[l] = nums1[i];
                    i++;
                    l++;
                    shuren *= -1;
                }else{
                    leftNums[l] = nums2[j];
                    j++;
                    l++;
                    shuren *= -1;
                }
            }
        }
        if(i == nums1.length){
            if(j == 0){
                if((nums1.length + nums2.length) % 2 == 0){
                    return ((leftNums[leftNums.length - 1] + nums2[j]) / 2.0);
                }else{
                    return nums2[j];
                }
            }else{
                if((nums1.length + nums2.length) % 2 == 0){
                    return (Math.max(leftNums[leftNums.length - 1] , nums2[j - 1]) + nums2[j]) / 2.0;
                }else{
                    return nums2[j];
                }
            }
        }
        if(j == nums2.length){
            if(i == 0){
                if((nums1.length + nums2.length) % 2 == 0){
                    return ((leftNums[leftNums.length - 1] + nums1[i]) / 2.0);
                }else{
                    return nums1[i];
                }
            }else{
                if((nums1.length + nums2.length) % 2 == 0){
                    return (Math.max(leftNums[leftNums.length - 1] , nums1[i - 1]) + nums1[i]) / 2.0;
                }else{
                    return nums1[i];
                }
            }
        }
        if((nums1.length + nums2.length) % 2 == 0){
            return ((leftNums[leftNums.length - 1] + Math.min(nums1[i],nums2[j])) / 2.0);
        }else{
            return Math.min(nums1[i],nums2[j]);
        }
    }

    public static void main(String[] args) {
        int[] arr1 = {100};
        int[] arr2 = {101};
        System.out.println(findMedianSortedArrays(arr1,arr2));
    }
}